package source.graph;

public class Graph {
    /**
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     * 此外，你可以假设该网格的四条边均被水包围。
     *
     * @param grid 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格
     * @return 计算网格中岛屿的数量
     */
    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }

        return res;
    }

    public void dfs(char[][] grid, int i, int j) {
        if (!inArea(grid, i, j) || grid[i][j] != '1')
            return;
        if (grid[i][j] == '1') {
            grid[i][j] = '2';
        }
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }

    public boolean inArea(char[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 && j < grid[i].length;
    }

    /**
     * 捕获 所有 被围绕的区域：
     * <p>
     * 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
     * 区域：连接所有 'O' 的单元格来形成一个区域。
     * 围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。
     * 通过 原地 将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值。
     *
     * @param board 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成
     */
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0)
            return;
        int row = board.length;
        int column = board[0].length;
        for (int i = 0; i < row; i++) {
            if (board[i][0] == 'O')
                dfs2(board, i, 0);
            if (board[i][column - 1] == 'O')
                dfs2(board, i, column - 1);
        }
        for (int i = 0; i < column; i++) {
            if (board[0][i] == 'O')
                dfs2(board, 0, i);
            if (board[row - 1][i] == 'O')
                dfs2(board, row - 1, i);
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                else if (board[i][j] == 'F') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs2(char[][] board, int i, int j) {
        if (!inArea(board, i, j) || board[i][j] == 'X')
            return;
        if (board[i][j] == 'O') {
            board[i][j] = 'F';
            dfs(board, i - 1, j);
            dfs(board, i + 1, j);
            dfs(board, i, j - 1);
            dfs(board, i, j + 1);
        }
    }
}